home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 2477 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.0 KB
  1. Path: mail2news.demon.co.uk!hpl3sn03.cern.ch
  2. From: Dan Pop <danpop@mail.cern.ch>
  3. Newsgroups: comp.lang.c
  4. Subject: Re: quick decision: is n a power of 2?
  5. Date: Sun, 21 Jan 1996 21:44:19 +0100
  6. Organization: CERN European Lab for Particle Physics
  7. Message-ID: <9601212044.AA18387@dxmint.cern.ch>
  8. References: <Pine.OSF.3.91.960119114608.18779E-100000@io.UWinnipeg.ca>     <4dpian$gij@oxy.rust.net> <9601201820.AA01752@dxmint.cern.ch> <TANMOY.96Jan21104404@qcd.lanl.gov>
  9. X-NNTP-Posting-Host: hpl3sn03.cern.ch
  10. X-Newsreader: NN version 6.5.0 #7 (NOV)
  11. X-Mail2News-Path: dxmint.cern.ch!hpl3sn03.cern.ch
  12.  
  13. tanmoy@qcd.lanl.gov (Tanmoy Bhattacharya) writes:
  14.  
  15. >In article <9601201820.AA01752@dxmint.cern.ch> Dan Pop
  16. ><danpop@mail.cern.ch> writes: 
  17. ><snip>
  18. >   >Given some number, there is a neat trick to generate a mask which will
  19. >   >have exactly one bit set in it.  The bit set will be the least
  20. >   >significant non-zero bit in the original number:
  21. >   >
  22. >   >    mask = ~number & number;
  23. >   >
  24. >   >Now, if number contained a single non-zero bit (and is therefore a
  25. >   >power of 2),  mask will be equal to number.  Therefore:
  26. >   >
  27. >   >   if (number == (~number & number))
  28. >   >   {
  29. >   >        /* number is a power of 2 */
  30. >   >   }
  31. >   >
  32. >   >Try it, you'll like it!
  33. >
  34. >   I don't think so.  ~number & number will _always_ give 0.  -number & number
  35. >   will actually work, except for the case when number == 0.  That is,
  36. >   assuming a two's complement implementation.  On a one's complement or
  37. >   sign-magnitude implementation it won't work at all.
  38. >
  39. >Consider x = 0...0101. -x = 1...1011
  40. >-x & x == 1. So I cannot quite figure out what was meant above.
  41.  
  42. And 1 != x, hence x is not a power of 2.  QED.
  43.  
  44. The proponent of the solution explained correctly how it works,
  45. unfortunately his solution didn't work as explained, so I fixed the
  46. solution to match the explanations :-)
  47.  
  48. Dan
  49. -- 
  50. Dan Pop
  51. CERN, CN Division
  52. Email: danpop@mail.cern.ch 
  53. Mail:  CERN - PPE, Bat. 31 R-004, CH-1211 Geneve 23, Switzerland
  54.